sgwt_laplacian : Compute graph laplacian from connectivity matrix function L = sgwt_laplacian(A,varargin) Connectivity matrix A must be symmetric. A may have arbitrary non-negative values, in which case the graph is a weighted graph. The weighted graph laplacian follows the definition in "Spectral Graph Theory" by Fan R. K. Chung Inputs : A - adjacency matrix Selectable Input parameters : 'opt' - may be 'raw' or 'normalized' (default raw) to select un-normalized or normalized laplacian Outputs : L - graph Laplacian
0001 % sgwt_laplacian : Compute graph laplacian from connectivity matrix 0002 % 0003 % function L = sgwt_laplacian(A,varargin) 0004 % 0005 % Connectivity matrix A must be symmetric. A may have arbitrary 0006 % non-negative values, in which case the graph is a weighted 0007 % graph. The weighted graph laplacian follows the definition in 0008 % "Spectral Graph Theory" by Fan R. K. Chung 0009 % 0010 % Inputs : 0011 % A - adjacency matrix 0012 % Selectable Input parameters : 0013 % 'opt' - may be 'raw' or 'normalized' (default raw) to select 0014 % un-normalized or normalized laplacian 0015 % 0016 % Outputs : 0017 % L - graph Laplacian 0018 0019 % This file is part of the SGWT toolbox (Spectral Graph Wavelet Transform toolbox) 0020 % Copyright (C) 2010, David K. Hammond. 0021 % 0022 % The SGWT toolbox is free software: you can redistribute it and/or modify 0023 % it under the terms of the GNU General Public License as published by 0024 % the Free Software Foundation, either version 3 of the License, or 0025 % (at your option) any later version. 0026 % 0027 % The SGWT toolbox is distributed in the hope that it will be useful, 0028 % but WITHOUT ANY WARRANTY; without even the implied warranty of 0029 % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 0030 % GNU General Public License for more details. 0031 % 0032 % You should have received a copy of the GNU General Public License 0033 % along with the SGWT toolbox. If not, see <http://www.gnu.org/licenses/>. 0034 0035 function L = sgwt_laplacian(A,varargin) 0036 control_params={'opt','raw'}; % or normalized 0037 argselectAssign(control_params); 0038 argselectCheck(control_params,varargin); 0039 argselectAssign(varargin); 0040 0041 N=size(A,1); 0042 if N~=size(A,2) 0043 error('A must be square'); 0044 end 0045 degrees=vec(full(sum(A))); 0046 % to deal with loops, must extract diagonal part of A 0047 diagw=diag(A); 0048 0049 % w will consist of non-diagonal entries only 0050 [ni2,nj2,w2]=find(A); 0051 ndind=find(ni2~=nj2); % as assured here 0052 ni=ni2(ndind); 0053 nj=nj2(ndind); 0054 w=w2(ndind); 0055 0056 di=vec(1:N); % diagonal indices 0057 0058 switch opt 0059 case 'raw' 0060 % non-normalized laplacian L=D-A 0061 L=sparse([ni;di],[nj;di],[-w;degrees-diagw],N,N); 0062 case 'normalized' 0063 % normalized laplacian D^(-1/2)*(D-A)*D^(-1/2) 0064 % diagonal entries 0065 dL=(1-diagw./degrees); % will produce NaN for degrees==0 locations 0066 dL(degrees==0)=0;% which will be fixed here 0067 % nondiagonal entries 0068 ndL=-w./vec( sqrt(degrees(ni).*degrees(nj)) ); 0069 L=sparse([ni;di],[nj;di],[ndL;dL],N,N); 0070 otherwise 0071 error('unknown option'); 0072 end